7/12
A
签到
B
签到
C
- 显然暴力是$2^{19} ·n$
- 预处理出每个相邻的字母的贡献。
- 时间复杂度$(2^{19}·19^2)$
D
题意
题解
E. Equal Numbers
题意
给一个 $n$ 和 $n$ 个数字，问可以修改 $k$ 次 $(0 \le k \le n)$，每次修改可以给任意一个数乘一个正整数，输出 $[0,n]$ 次修改的情况下，最少不相同数字数量。
题解
- 令 $goal=lcm(a1,a2,…,an)$。
- 那么对于每种数，可以变成另一个存在的倍数，或者直接变成 $goal。$
- 时间复杂度: $O(nlogn)$
I. Intelligence in Perpendicularia
- 赛时沙雕写了个线段树。
- 暴力维护多边形的边界即可。
- 答案就是多边形的变长减去边界。
K. Kotlin Island
题意
给出网格图的长和宽，可以填满整行和整列，输出构造出分割成 $n$ 个区域的的解法。
题解
- 行最多可以添加 $\frac{h-1}{2}$条边 ,列同理。
- 假设添加了 $x$ 行 $y$ 列，那么区域数量为 $(x + 1) · (y + 1)$。
- 枚举 $x$ ，check是否存在合法的 $y$ 即可。
L. Little Difference
czh solved